0. Introduction

바빌로니안 place-value number system.

숫자 "123"에서 1과 2와 3은 각각 다른 값을 가진다. 1은 100, 2는 20을, 3은 3을 의미한다. 로마 숫자는 그 숫자의 갯수에 따라 값이 결정되지, 위치는 중요하지 않다. 달까지의 거리인 259,956마일을 나타내기 위해서는 다음과 같이 많은 숫자를 나열해야 한다. $MMM.........MMMDCCCCLVI$ 그런데 태양까지의 거리를 로마 숫자로 나타내려면 무려 100,000 십만개의 글자가 있어야 된다. 당연히 바빌로니안 체계가 편리하고 유용하고 우월하다고 볼 수 있다.

In the language of Computer Science, the place-value system for representing numbers is known as a data structure: a set of instructions, or “recipe”, for representing objects as symbols. An algorithm is a set of instructions, or “recipe”, for performing operations on such representations.

컴퓨터 과학에서 '데이터 구조'라고 불리는게 바로 이런 것이다. 수를 place-value system을 통해 표현하는것. (맨 오른쪽 숫자는 1의 자리, 그 왼쪽의 숫자는 10의 자리, 100의 자리, 1000의 자리 등). 어떤것을 기호로 표현하기 위한 지침들을 데이터 구조라고 한다. '알고리즘' 이라고 불리는 것들은 이런 기호 표현들을 가지고 연산을 수행하는 지침들을 말한다.

바빌로니안들은 또한 "standard algorithms"라는것도 발명했는데, 곱셈과 같은 사칙연산을 말한는 것 같다. 잘 알려진 두 수를 곱하는 방법으로는 다음과 같은 방법이 있다.

1. 숫자 x,y가 있으면 x를 y번 더하는 것.
2. Grade-school multiplication이라는데, 두 숫자 x와 y를 각 자리의 숫자들을 따로 떼서 곱셈하는 것.

grade-school multiplication은 그니까 어린시절 수학시간에 배웠던 곱셈법이다. 123과 456을 곱하면, $3 * 6$ 을 먼저 하고 $3 * 5$를 하고 ....

이 방법을 통해서 연산을 하면 특히 큰 숫자끼리 곱할때는 1번의 방법보다 엄청 효율적이라고 한다. 20자리 숫자끼리 곱한다고 하면 1번 방법으로는 $10^{19}$ 번의 덧셈을 해야하는데 2번 방법으로는 $2(20^2)$번의 곱셈으로 충분하다고.

일단 먼저 각 숫자끼리 곱하는 횟수가 $20^2$ 번이 있다. $1234 * 5678$을 하면 4를 각 5,6,7,8과 곱하니 4번의 곱셈이 있고, 나머지 3과 2와 1도 마찬가지니까, $4^2$ = 16번의 계산을 한다는 것.

그러면 앞의 2는? 자리올림, 위에서 result에 값을 더하면서 $10^{i+j}$와 곱해주는데 이 곱셈까지 한번씩 더 하니까 $n^2$의 계산을 한번 더 하니 $2(n^2)$번의 연산이 이루어지는것.